home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / brklyprl.lha / Emulator / string_table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-14  |  4.2 KB  |  197 lines
  1.  
  2. /* Copyright (C) 1988, 1989 Herve' Touati, Aquarius Project, UC Berkeley */
  3.  
  4. /* Copyright Herve' Touati, Aquarius Project, UC Berkeley */
  5.  
  6. #include <stream.h>
  7. #include "hash_table.h"
  8. #include "string_table.h"
  9.  
  10. inline char* external(int i) {return (char*) i;}
  11. inline int internal(char* s) {return (int) s;}
  12.  
  13.  
  14.  
  15. char* StringTable::save_string_copy(char* s)
  16. {
  17.   extern int strcpy(char*,char*);
  18.   extern int strlen(char*);
  19.   int len = strlen(s) + 1;
  20.   char* new_str = new_string(len);
  21.   strcpy(new_str, s);
  22.   return new_str;
  23. }
  24.  
  25. StringTable::StringTable(int string_size, int hash_size) : (hash_size)
  26. {
  27.   string_space_size = string_size;
  28.   alloc_string_space();
  29. }
  30.  
  31. void StringTable::alloc_string_space()
  32. {
  33.   char* malloc(int);
  34.   next_string = malloc(string_space_size * sizeof(char));
  35.   string_space_left = string_space_size;
  36.   if (next_string == 0) {
  37.     cout << "Symbol Table Overflow\n";
  38.     exit(1);
  39.   }
  40. }
  41.  
  42. char* StringTable::new_string(int len)
  43. {
  44.   if (string_space_left < len + 8) {
  45.     string_space_size <<= 1;
  46.     alloc_string_space();
  47.   }
  48.   int residue = ((int) next_string - 4) % 8;
  49.   if (residue != 0) {
  50.     next_string += 8 - residue;
  51.     string_space_left -= 8 - residue;
  52.   }
  53.   char* result = next_string;
  54.   next_string += len;
  55.   string_space_left -= len;
  56.   return result;
  57. }
  58.  
  59. unsigned string_hash(char* s)
  60. {
  61.   register unsigned h;
  62.   register char* p = s;
  63.   for (h = 0; *p != '\0'; p++)
  64.     h += *p;
  65.   return h;
  66. }  
  67.  
  68. extern int strcmp(char*,char*);
  69. inline unsigned string_equal(char* a, char* b)
  70. {
  71.   return (strcmp(a, b)) ? 0 : 1;
  72. }
  73.  
  74. void StringTable::reenter_old_data(int old_size, HashTableEntry** old_table)
  75. {
  76.   register HashTableEntry** c;
  77.   for (int i = 0; i < old_size; i++) {
  78.     c = &old_table[i];
  79.     while (*c != 0) {
  80.       reintern((*c)->key, (*c)->value);
  81.       c = &((*c)->next);
  82.     }
  83.   }
  84. }
  85.  
  86. void StringTable::rehash()
  87. {
  88.   void free(char*);
  89.   char* old_alloc_area = alloc_area;
  90.   HashTableEntry** old_table = table;
  91.   int old_size = size;
  92.   size <<= 1;
  93.   allocate();
  94.   reenter_old_data(old_size, old_table);
  95.   free(old_alloc_area);
  96. }
  97.  
  98. void StringTable::reintern(int key, int value) 
  99. {
  100.   unsigned h = string_hash(external(key));
  101.   HashTableEntry** c = &table[h % size];
  102.   while (*c != 0)
  103.     c = &((*c)->next);
  104.   if ((*c = new_cell()) == 0) {
  105.     cerr << "Error in rehashing\n";
  106.     exit(1);
  107.   }
  108.   (*c)->next = 0;
  109.   (*c)->key = key;
  110.   (*c)->value = value;
  111. }
  112.  
  113. int StringTable::intern(char* s) 
  114. {
  115.   unsigned h = string_hash(s);
  116.   HashTableEntry** c = &table[h % size];
  117.   while (*c != 0 && ! string_equal(external((*c)->key), s))
  118.     c = &((*c)->next);
  119.   if (*c == 0) {
  120.     if ((*c = new_cell()) == 0) {
  121.       rehash();
  122.       return intern(s);
  123.     }
  124.     (*c)->next = 0;
  125.     (*c)->value = -1;
  126.     (*c)->key = internal(save_string_copy(s));
  127.   }
  128.   return (*c)->key;
  129. }
  130.  
  131. void StringTable::print()
  132. {
  133.   reset();
  134.   HashTableEntry* e;
  135.   while (e = next())
  136.     printf("\"%s\" %d %d\n", 
  137.        external(e->key),
  138.        e->key, 
  139.        string_hash(external(e->key)) % size);
  140. }
  141.  
  142. static int compute_arity(char* s)
  143. {
  144.   int atoi(const char*);
  145.   char* rindex(char*, char);
  146.   s = rindex(s, '/');
  147.   return (s == 0) ? 0 : atoi(s + 1);
  148. }
  149.  
  150. int StringTable::get_arity(int name)
  151. {
  152.   int arity = arity_table.get(name);
  153.   if (arity_table.status == HASH_MISS) {
  154.     arity = compute_arity(external(name));
  155.     arity_table.bind(name, arity);
  156.   }
  157.   return arity;
  158. }
  159.  
  160. static int check_length(char* s, int limit)
  161. {
  162.   extern int strlen(char*);
  163.   int len = strlen(s) + 1;
  164.     if (len > limit) {
  165.     cout << "string longer than buffer size: internal limit\n";
  166.     exit(1);
  167.   }
  168.   return len;
  169. }
  170.  
  171. int StringTable::atom_to_functor(int atom, int arity)
  172. {
  173.   static char buffer[256];
  174.   extern int strlen(char*);
  175.   int len = check_length(external(atom), 256);
  176.   extern int sprintf(char*, const char*, ...);
  177.   sprintf(buffer, "%s/%d", external(atom), arity);
  178.   int result = intern(buffer);
  179.   arity_table.bind(result, arity);
  180.   return result;
  181. }
  182.   
  183. int StringTable::functor_to_atom(int functor)
  184. {
  185.   char buffer[256];
  186.   extern int strlen(char*);
  187.   int len = check_length(external(functor), 256);
  188.   extern int strcpy(char*, char*);
  189.   strcpy(buffer, external(functor));
  190.   extern char* rindex(char*, char);
  191.   char* p = rindex(buffer, '/');
  192.   if (p != 0) *p = '\0';
  193.   int result = intern(buffer);
  194.   return result;
  195. }
  196.  
  197.